Schleife (Graphentheorie)

Als Schleife oder Schlinge wird in der Graphentheorie eine Kante bezeichnet, die einen Knoten mit sich selbst verbindet.^[1][2] Jede Schlinge bildet einen Kreis der Länge eins in dem Graphen.

Je nach Kontext können Graphen so definiert werden, dass sie Schlingen zulassen oder ausschließen (oft in Verbindung mit der Zulassung von Mehrfachkanten):

• Lässt man Schleifen oder Mehrfachkanten in der Definition von Graphen zu, wird ein Graph ohne Schleifen und Mehrfachkanten zur Unterscheidung als Einfacher Graph bezeichnet. Ein Graph ohne Schleifen wird schleifenloser, schleifenfreier oder schlingenfreier Graph genannt.
• Schließt man Schleifen und Mehrfachkanten in der Definition von Graphen aus, wird ein Graph mit Schleifen oder Mehrfachkanten zur Unterscheidung als Multigraph bezeichnet.

1. ↑ Guido Walz (Hrsg.): Lexikon der Mathematik – Band 4. 2. Auflage. Springer, 2017, ISBN 978-3-662-53500-4, S. 463, Stichwort Schlinge eines Graphen, doi:10.1007/978-3-662-53500-4. 
2. ↑ Lukas Pottmeyer: Diskrete Mathematik. Springer, 2019, ISBN 978-3-662-59662-3, S. 78, doi:10.1007/978-3-662-59663-0_4 (verwendet die Bezeichnung Schleife).